package MyDFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * 139. 单词拆分
 *
 * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 *
 * 说明：
 *
 *     拆分时可以重复使用字典中的单词。
 *     你可以假设字典中没有重复的单词。
 *
 * 示例 1：
 *
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 *
 * 示例 2：
 *
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 *      注意你可以重复使用字典中的单词。
 */
public class Leetcode0193 {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> hs = new HashSet<>();
        //超时优化1 存储字典中的长度
        HashSet<Integer> count = new HashSet<>();
        // 超时优化3 加入字符判断策略
        int[] dict = new int[26];
        for(String w : wordDict){
            hs.add(w);
            count.add(w.length());
            for(int i=0; i<w.length(); i++){
                dict[w.charAt(i) - 'a'] ++;
            }
        }

        for(int i=0; i<s.length(); i++){
            if(dict[s.charAt(i) - 'a'] <= 0){
                return false;
            }
        }

        int[] cnt = new int[count.size()];
        int cnt_idx = 0;
        for(Integer cc : count){
            cnt[cnt_idx++] = cc;
        }
        Arrays.sort(cnt);


        List<Integer> ans = new ArrayList<>();
        int len = s.length();
        dfs(hs, cnt, s, len, 0, ans);
        return ans.size() > 0;
    }

    public void dfs(HashSet<String> hs, int[] cnt, String s, int len, int idx, List<Integer> ans){
        // System.out.println("=" + idx);
        if(idx == len){
            ans.add(1);
            return;
        }
        // 超时优化2 只要找到就结束
        if(ans.size() >= 1){
            return;
        }
        // 超时优化4 倒序查找 从长的开始挑
        for(int i=cnt.length-1; i>=0; i--){
            int cc = cnt[i];
            if(idx+cc <= len && hs.contains(s.substring(idx, idx + cc))){
                dfs(hs, cnt, s, len, idx+cc, ans);
            }
        }
    }

}
